package LeetCode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class LC_493_ReversePairs {

    public static void main(String[] args) {

    }

    public class Solution {
        public int reversePairs(int[] nums) {
            int res = 0;
            int n = nums.length;
            if (n == 0) return res;
            Map<Long, Integer> map = new HashMap<>();
            long[] sorted = new long[2 * n];
            for (int i = 0; i < n; i++) {
                sorted[2 * i] = nums[i];
                sorted[2 * i + 1] = (long) nums[i] * 2;
            }
            Arrays.sort(sorted);
            int idx = 1;
            for (long num : sorted) {
                if (!map.containsKey(num)) map.put(num, idx++);
            }

            BIT t = new BIT(idx);
            int sum = 0;
            for (int num1 : nums) {
                long num = (long) num1;
                res += sum - t.sum(map.get(num * 2));
                t.add(map.get(num));
                sum++;
            }
            return res;
        }

        class BIT {
            int n;
            int[] tree;

            BIT(int n) {
                this.n = n;
                tree = new int[n];
            }

            int sum(int i) {
                int res = 0;
                while (i > 0) {
                    res += tree[i];
                    i -= i & -i;
                }
                return res;
            }

            void add(int i) {
                while (i < n) {
                    tree[i] += 1;
                    i += i & -i;
                }
            }
        }

    }
}